package codetop.microsoft.T287;

/**
 * @Author: 18362
 * @Create: 2022-08-15 17:24:39 星期一
 */
class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cnt = 0, total = right - left + 1;
            for (int i=0; i<nums.length; ++i) {
                if (nums[i] <= mid)
                    cnt++;
            }
            if (cnt <= mid)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}